/*
 * @lc app=leetcode.cn id=494 lang=golang
 *
 * [494] 目标和
 */

// @lc code=start
func findTargetSumWays(nums []int, target int) int {
	// 此题涉及一个问题转换
	// 将最终式中加法所得数字设为 x，那么减法的和为 sum -x
	// 也就是最终需要 x - （sum - x） = target
	// 可以推出 x = （sum+target）/2
	// 计算出 nums 组成 x 的方法数目就可以获取到最终的方法数了
	sum:=0
	for _,v:=range nums{
		sum +=  v 
	}
	if (sum+target)%2 == 1{
		return 0
	}
	n:=len(nums)
	x:= (sum+target)/2
	// dp[i][j] 表示 0-i 个数字组成 j 的方法数
	dp := make([][]int,n+1)
	for i,_:=range dp{
		dp[i] = make([]int,x+1)
	}
	// for i:=0;i<=n;i++{
	// 	dp[i][0] = 1
	// }
	dp[0][0] = 1
	for i:=1;i<=n;i++{
		for j:=0;j<=x;j++{
			if j>=nums[i-1]{
				// 不选当前数和选当前数的方法相加，就是当前数加入数组，组成 j 的方法数目
				dp[i][j] = dp[i-1][j-nums[i-1]]+dp[i-1][j]
			}else{
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	// fmt.Println(dp)
	return dp[n][x]
}

func max(i,j int)int{
	if i>j{
		return i 
	}
	return j
}
// @lc code=end

